package com.mdnote.jianzhi_offer.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/18
 * @description 剑指 Offer 14- I. 剪绳子
 */
public class Offer14I {

    public int cuttingRope(int n) {
//        return dp(n)
        return greedy(n);
    }

    private int greedy(int n) {
        if (n < 2) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }
        int cut3 = n / 3;

        if (n - cut3 * 3 == 1) {
            cut3--;
        }

        int cut2 = (n - cut3 * 3) / 2;

        return (int) (Math.pow(3, cut3)) * (int) (Math.pow(2, cut2));
    }

    private int dp(int n) {
        // 分析一下题目
        // 状态：当前长度i，选择：剪 or 不剪
        // DP[i] I 当前需要处理的绳子长度，dp[i] 最大乘积
        // 状态转换方程  dp[n] = Max {for i in range(n) : dp[i] * dp[n - i]}
        if (n < 2) {
            return n;
        }
        if (n == 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int[] dp = new int[n + 1];

        /// base case
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;


        for (int m = 4; m < dp.length; m++) {
            for (int i = 1; i <= m / 2; i++) {
                dp[m] = Math.max(dp[m], dp[i] * dp[m - i]);
            }
        }

        return dp[n];
    }
}
